import sys
I = lambda: [*map(int, sys.stdin.readline().split())]
def consec(a):
tot = 0
big = float('inf')
neg = 0
for guy in a:
tot += abs(guy)
if abs(guy) < big:
big = abs(guy)
if guy < 0:
neg += 1
if neg % 2 == 0:
return (tot, tot - 2 * big)
return (tot - 2 * big, tot)
import math
def main():
n, m = I()
a = I()
b = I()
g = b[0]
for i in range(1, m):
g = math.gcd(g, b[i])
if g == 1:
print(sum(abs(guy) for guy in a))
return
tot = 0
tot1 = 0
for i in range(g):
guy = []
j = i
while j < n:
guy.append(a[j])
j += g
x, y = consec(guy)
tot += x
tot1 += y
print(max(tot, tot1))
t, = I()
for _ in range(t):
main()#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef long long ll;
ll getmax(vector<ll> nums) {
ll best_unflipped = nums[0];
ll best_flipped = -nums[0];
for (int i = 1; i < nums.size() - 1; i++) {
ll new_best_unflipped = -(1e18);
ll new_best_flipped = -(1e18);
// flip this one
new_best_flipped = max(best_flipped + nums[i], best_unflipped - nums[i]);
// not
new_best_unflipped = max(best_flipped - nums[i], best_unflipped + nums[i]);
best_flipped = new_best_flipped;
best_unflipped = new_best_unflipped;
}
best_flipped -= nums[nums.size() - 1];
best_unflipped += nums[nums.size() - 1];
// cout << best_flipped << " " << best_unflipped << endl;
return max(best_flipped, best_unflipped);
}
void solve() {
int n; cin >> n;
int m; cin >> m;
vector<ll> nums(n);
for (auto &a : nums) cin >> a;
vector<int> b(m);
for (auto &a : b) cin >> a;
int overall_gcd = b[0];
for (auto x : b) overall_gcd = __gcd(x, overall_gcd);
if (overall_gcd == 1) {
ll t = 0;
for (int i = 0; i < n; i++) t += abs(nums[i]);
cout << t << endl;
return;
}
// overall_gcd -= 1;
ll total_flip = 0;
ll total_unflip = 0;
for (int i = 0; i < overall_gcd; i++) {
vector<ll> newnums;
for (int j = i; j < n; j += overall_gcd) {
newnums.push_back(nums[j]);
}
total_unflip += getmax(newnums);
newnums[0] = -newnums[0];
// if (i == 0) newnums[1] = -newnums[1];
// for (auto a : newnums) cout << a << " ";
// cout << endl;
total_flip += getmax(newnums);
}
cout << max(total_flip, total_unflip) << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int tt = 1;
cin >> tt;
while (tt--) solve();
return 0;
}112. Path Sum | 1556A - A Variety of Operations |
136. Single Number | 169. Majority Element |
119. Pascal's Triangle II | 409. Longest Palindrome |
1574A - Regular Bracket Sequences | 1574B - Combinatorics Homework |
1567A - Domino Disaster | 1593A - Elections |
1607A - Linear Keyboard | EQUALCOIN Equal Coins |
XOREQN Xor Equation | MAKEPAL Weird Palindrome Making |
HILLSEQ Hill Sequence | MAXBRIDGE Maximise the bridges |
WLDRPL Wildcard Replacement | 1221. Split a String in Balanced Strings |
1002. Find Common Characters | 1602A - Two Subsequences |
1555A - PizzaForces | 1607B - Odd Grasshopper |
1084A - The Fair Nut and Elevator | 1440B - Sum of Medians |
1032A - Kitchen Utensils | 1501B - Napoleon Cake |
1584B - Coloring Rectangles | 1562B - Scenes From a Memory |
1521A - Nastia and Nearly Good Numbers | 208. Implement Trie |